#define  _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>

using namespace std;

//使用最小花费爬楼梯
//法一：到结尾
class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost)
    {
        int n = cost.size();
        //创建dp表
        vector<int> dp(n + 1);
        //初始化
        dp[0] = 0;
        dp[1] = 0;
        //填表
        for (int i = 2; i <= n; i++)
            dp[i] = min(dp[i - 2] + cost[i - 2], dp[i - 1] + cost[i - 1]);

        //返回最低花费

        return dp[n];

    }
};
//法二：从开始
class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int n = cost.size();
        //创建dp表
        vector<int> dp(n);

        //初始化
        dp[n - 1] = cost[n - 1];
        dp[n - 2] = cost[n - 2];

        //填表
        for (int i = n - 3; i >= 0; i--)
            dp[i] = min(dp[i + 1] + cost[i], dp[i + 2] + cost[i]);

        //返回值
        return min(dp[0], dp[1]);


    }
};

int main()
{

	return 0;;
}